package luo.hui.jiang.binarysearchoecursion.floyd;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 弗洛伊德算法
 * 思路：
 * 首先准备两个数组dis 和 pre
 * dis ： 用来存储我们点到点的距离
 * pre ： 用来存储我们点的前一个节点的点。
 * 初始化的时候， dis 等于邻接矩阵
 * pre 所节点等于自己 fill方法来实践
 * <p>
 * 第一层遍历 ：然后就是去遍历我们的节点 有多少中节点遍历多少次 dis.length
 * 第二，三层遍历 ：然后在对我们的邻接矩阵进行遍历 ，循环的比较整个邻接矩阵。
 * 如果我们 以 第一层遍历的节点为中间节点得到的距离小于我们原本在邻接矩阵中的距离。
 * 那么就修改之。
 * <p>
 * 最后经过这些遍历后。我们就会得到每个节点到其他节点的最短距离。
 *
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/8/25 15:56
 */
public class FloydAlgorihm {

	public static void main(String[] args) {
		// 测试看看图是否创建成功
		char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//创建邻接矩阵
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;
		matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
		matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
		matrix[2] = new int[]{7, N, 0, N, 8, N, N};
		matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
		matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
		matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
		matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};

		//创建 Graph 对象
		Graph graph = new Graph(vertex.length, matrix, vertex);
		//调用弗洛伊德算法
		graph.floyd2();
		graph.show();
	}
}

class Graph {
	private char[] vertex; // 存放顶点的数组
	private int[][] dis; // 保存，从各个顶点出发到其他顶点的距离，最后的结果，也是保留在该数组
	private int[][] pre; // 保存到达目标顶点的前驱顶点

	// 构造器，
	public Graph(int length, int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new int[length][length];
		// 对于 pre 数组的初始化，注意存放的是前驱顶点的下标
		for (int i = 0; i < length; i++) {
			Arrays.fill(pre[i], i);
		}
	}

	// 显示pre 数组和dis 数组
	public void show() {
		// 为了 显示便于阅读，我们优化一下输出
		char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		for (int i = 0; i < dis.length; i++) {
			// 先将pre数组输出的一行
			for (int j = 0; j < dis.length; j++) {
				System.out.print(vertex[pre[i][j]] + " ");
			}
			System.out.println();
			// 输出 dis 数组的一行数据
			for (int j = 0; j < dis.length; j++) {
				System.out.print("(" + vertex[i] + "到" + vertex[j] + "的最短路径是" + dis[i][j] + ")");
			}
			System.out.println();
			System.out.println();
		}
	}

	public void floyd() {
		int len = 0;//变量保存距离
		// 对中间顶点遍历，k 就是中间顶点的下标 [A,B,C,D,E,F,G]
		for (int k = 0; k < dis.length; k++) { //
			//从i顶点开始出发 [A, B, C, D, E, F, G]
			for (int i = 0; i < dis.length; i++) {
				//到达j顶点 // [A, B, C, D, E, F, G]
				for (int j = 0; j < dis.length; j++) {
					len = dis[i][k] + dis[k][j];// => 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
					if (len < dis[i][j]) {//如果len小于 dis[i][j]
						dis[i][j] = len;//更新距离
						pre[i][j] = pre[k][j];//更新前驱顶点
					}
				}
			}
		}
	}

	public void floyd1() {
		int len = 0;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis.length; j++) {
				for (int k = 0; k < dis.length; k++) {
					len = dis[j][i] + dis[i][k];
					if (len < dis[j][k]) {
						dis[j][k] = len;
						pre[j][k] = pre[i][k];
					}
				}
			}
		}
	}

	public void floyd2() {
		int len = 0;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis.length; j++) {
				for (int k = 0; k < dis.length; k++) {
					len = dis[j][i] + dis[i][k];
					if (len < dis[j][k]) {
						dis[j][k] = len;
						pre[j][k] = pre[i][k];
					}
				}
			}
		}
	}
}
